An Efficient Algorithm for Hamiltonian Path Embedding of k -Ary n -Cubes Under the Partitioned Edge Fault Model
一种在划分边故障模型下对 k -元 n -立方体进行哈密顿路径嵌入的高效算法

Hongbin Zhuang ©, Xiao-Yan Li D, Jou-Ming Chang (C), and Dajin Wang (C)
郑红宾 ©, 李晓燕 D, 张觉明 (C), 以及王大金 (C)
Abstract-The k -ary n -cube Qnk is one of the most important interconnection networks for building network-on-chips, data center networks, and parallel computing systems owing to its desirable properties. Since edge faults grow rapidly and the path structure plays a vital role in large-scale networks for parallel computing, fault-tolerant path embedding and its related problems have attracted extensive attention in the literature. However, the existing path embedding approaches usually only focus on the theoretical proofs and produce an n -related linear fault tolerance since they are based on the traditional fault model, which allows all faults to be adjacent to the same node. In this paper, we design an efficient fault-tolerant Hamiltonian path embedding algorithm for enhancing the fault-tolerant capacity of k -ary n -cubes. To facilitate the algorithm, we first introduce a new conditional fault model, named Partitioned Edge Fault model (PEF model). Based on this model,for the k -ary n -cube Qnk with n2 and odd k3 ,we explore the existence of a Hamiltonian path in Qnk with large-scale edge faults. Then we give an O(N) algorithm,named HP-PEF, to embed the Hamiltonian path into Qnk under the PEF model, where N is the number of nodes in Qnk . The performance analysis of HP-PEF shows the average path length of adjacent node pairs in the Hamiltonian path constructed by HP-PEF. We also make comparisons to show that our result of edge fault tolerance has exponentially improved other known results. We further experimentally show that HP-PEF can support the dynamic degradation of average success rate of constructing Hamiltonian paths when increasing faulty edges exceed the fault tolerance.
摘要- k -元 n -立方体 Qnk 是构建网络芯片、数据中心网络和并行计算系统最重要的互联网络之一,这要归功于其理想的特性。由于边缘故障迅速增长,并且在并行计算的大规模网络中路径结构发挥着至关重要的作用,因此在文献中,容错路径嵌入及其相关问题已经引起了广泛的关注。然而,现有的路径嵌入方法通常只关注理论证明,并且由于它们基于传统的故障模型,该模型允许所有故障与同一节点相邻,因此它们产生了与 n 相关的线性故障容忍度。在本文中,我们设计了一种高效的容错哈密顿路径嵌入算法,以提高 k -元 n -立方体的故障容忍能力。为了便于算法的实现,我们首先引入了一种新的条件故障模型,名为分区边缘故障模型(PEF模型)。基于这个模型,对于具有 n2 和奇数 k3k -元 n -立方体 Qnk,我们探讨了在存在大规模边缘故障的 Qnk 中哈密顿路径的存在性。然后我们给出了一种名为HP-PEF的算法,用于在PEF模型下将哈密顿路径嵌入到 Qnk 中,其中 NQnk 中的节点数。HP-PEF的性能分析显示了由HP-PEF构建的哈密顿路径中相邻节点对的平均路径长度。我们还进行了比较以显示我们的边缘故障容忍结果指数级地优于其他已知结果。我们进一步通过实验表明,当增加的故障边超过故障容忍度时,HP-PEF可以支持构建哈密顿路径的平均成功率动态下降。
Index Terms- k -ary n -cubes,algorithm,fault-tolerant embedding, Hamiltonian path, interconnection networks.
索引术语- k -元 n -立方体,算法,容错嵌入,哈密顿路径,互联网络。

NOMENCLATURE
名词术语表

NoC Network-on-Chip
NoC 芯片上网络
TSV Through silicon via
TSV 硅微孔
IC Integrated circuit
IC 集成电路
VLSI Very large scale integration
VLSI 超大规模集成电路
TRC Tours routing chip
TRC 旅行路由芯片
DCN Data center network
DCN 数据中心网络
H-path Hamiltonian path
H-path 哈密顿路径
PEF Partitioned edge fault
PEF 分区边缘故障
Qnkk -Ary n -cube
Qnkk -Ary n -立方体
APL Average path length
APL 平均路径长度
SD Standard deviation
SD 标准差
FT Fault tolerance of Qnk when embedding the H-path under the traditional model
FT 在传统模型下嵌入 H 路径时的 Qnk 容错性
FP Fault tolerance of Qnk when embedding the H-path under the PEF model
FP 在 PEF 模型下嵌入 H 路径时的 Qnk 容错性
ASR Average success rate
ASR 平均成功率

I. INTRODUCTION
I. 引言

NETWORK-ON-CHIPS (NoCs) have emerged as a promis- ing fabric for supercomputers due to their reusability and scalability [1], [2]. This fabric allows a chip to include a large number of computing nodes and effectively turn it into a tiny supercomputer. Therefore, it alleviates the bottlenecks faced by the further development of supercomputers. With the rapidly increasing demand for computing capacity, the number of on-chip cores increases quickly, which results in a high average internode distance in two-dimensional NoCs (2D NoCs). Consequently, 2D NoCs exhibit high communication delay and power consumption as the scale of networks increases [3]. Hence, 3D NoCs have been designed to solve the scalability problem of 2D NoCs. In 3D NoCs, the so-called through silicon via (TSV) links are used to connect various planes or layers. Though the fabrication cost of TSV links is quite high, 3D NoCs can reduce the probability of long-distance communication while still maintaining high integration density.
网络-芯片(NoCs)因其可重用性和可扩展性 [1], [2] 而成为超级计算机的有前景的架构。这种架构允许芯片包含大量的计算节点,并有效地将其转变为微型超级计算机。因此,它缓解了超级计算机进一步发展所面临的瓶颈。随着计算容量的需求迅速增长,芯片上的核心数量快速增加,这导致二维网络-芯片(2D NoCs)中的平均节点间距离较高。因此,随着网络规模的增加,2D NoCs 显示出较高的通信延迟和功耗 [3]。因此,三维 NoCs 被设计出来以解决 2D NoCs 的可扩展性问题。在 3D NoCs 中,所谓的硅微孔(TSV)连接用于连接不同的平面或层。尽管 TSV 连接的制造成本相当高,但 3D NoCs 能够在保持高集成密度的同时减少远距离通信的概率。
However, since the additional expense is required for incorporating more processing nodes, NoCs demand a robust fault tolerance. For example, 3D integrated circuit (IC) fabrication technology improves the power density of modern chips, which results in a thermal-intensive environment for 3D NoCs. High core temperatures reduce chip lifetime and mean time to failure, as well as resulting in low reliability and high cooling costs. The faults in NoCs are mainly divided into two categories, namely, transient faults and permanent faults. Generally speaking, permanent fault deserves more attention [4] since it seriously affects the transmission of more packets. With the rapid increase in the number of processing nodes, NoCs may encounter many permanent faults problems [5], and more reliability threats accompanied by permanent faults will also appear [6]. Therefore, we mainly discuss the permanent faults in this paper.
然而,由于需要额外费用来集成更多的处理节点,NoCs(网络芯片)需要具备强大的容错能力。例如,3D集成电路(IC)制造技术提高了现代芯片的功率密度,导致3D NoCs面临热密集环境。高核心温度会缩短芯片寿命和平均故障间隔时间,同时导致可靠性降低和冷却成本增加。NoCs中的故障主要分为两类,即暂时性故障和永久性故障。一般来说,永久性故障更值得关注[4],因为它严重影响更多数据包的传输。随着处理节点数量的快速增加,NoCs可能会遇到许多永久性故障问题[5],并且伴随着永久性故障的可靠性威胁也会出现[6]。因此,本文主要讨论永久性故障。

Manuscript received 23 July 2022; revised 4 February 2023; accepted 1 April 2023. Date of publication 5 April 2023; date of current version 8 May 2023. This work was supported by the National Natural Science Foundation of China under Grant 62002062 (X.-Y. Li), in part by the Ministry of Science and Technology of Taiwan under Grant MOST-111-2221-E-141-006 (J.-M. Chang), and in part by the Natural Science Foundation of Fujian Province under Grant 2022J05029 (X.-Y. Li). Recommended for acceptance by D. Yang. (Corresponding author: Xiao-Yan Li.)
手稿于2022年7月23日收到,于2023年2月4日修订,于2023年4月1日接受。发表日期为2023年4月5日;当前版本日期为2023年5月8日。这项工作得到了中国国家自然科学基金资助(项目编号62002062,李晓燕),部分得到了台湾科技部资助(项目编号MOST-111-2221-E-141-006,张俊明),以及部分得到了福建省自然科学基金资助(项目编号2022J05029,李晓燕)。由杨德推荐接受。(通讯作者:李晓燕)
Hongbin Zhuang and Xiao-Yan Li are with the College of Computer and Data Science, Fuzhou University, Fuzhou 350108, China (e-mail: hbzhuang476@gmail.com; xyli@fzu.edu.cn).
郑红宾和李晓燕均任职于福州大学计算机与数据科学学院,福州350108,中国(电子邮件:hbzhuang476@gmail.com; xyli@fzu.edu.cn)。
Jou-Ming Chang is with the Institute of Information and Decision Sciences, National Taipei University of Business, Taipei 10051, Taiwan (e-mail: spade@ntub.edu.tw).
张乔铭是台湾台北商业大学信息与决策科学研究所的成员,地址:台湾台北10051 (电子邮件:spade@ntub.edu.tw)。
Dajin Wang is with the Department of Computer Science, Montclair State University, Montclair, NJ 07043 USA (e-mail: wangd@montclair.edu).
汪大金是蒙特克莱尔州立大学计算机科学系的成员,地址:美国新泽西州蒙特克莱尔07043 (电子邮件:wangd@montclair.edu)。
Digital Object Identifier 10.1109/TPDS.2023.3264698
数字对象标识符 10.1109/TPDS.2023.3264698

A well-designed fault-tolerant routing algorithm can address the fault tolerance challenges of NoCs by bypassing the faults when delivering packets. Routing algorithms should be not only fault-tolerant but also deadlock-free. The Hamiltonian path (H-path for short) strategy is a powerful tool for deadlock avoidance. Since the H-path traverses every node in the network exactly once and contains no cycle structure, the deadlock can be easily prevented by transmitting the packets along the H-path [7], [8], [9], [10], [11], [12], [13]. In recent years, this excellent strategy is utilized for designing fault-tolerant routing algorithms. For instance, the HamFA algorithm [7] is one of the most famous fault-tolerant routing algorithms using the H-path strategy. It constructs two directed subnetworks through the H -path strategy and limits packets to be routed in a single subnetwork so that the deadlock can be avoided. Simultaneously, HamFA can tolerate almost all one-faulty links. The FHOE algorithm [8] is also a fault-tolerant routing algorithm based on the H-path strategy for 2D NoCs. It fully combines the advantages of traditional odd-even turn model and HamFA strategy, and consequently can provide higher adaptivity and more choices of minimal paths compared to HamFA. Considering the importance of fault tolerance and extensive applications of the H-path in NoCs, it's natural to investigate the existence of the H-path in NoCs (i.e., the problem of embedding the H-path into NoCs), especially when faults occur (i.e., the fault-tolerant problem of embedding the H-path into NoCs). However, it is well-known that the problem of embedding an H -path into a network is NP-complete, even when no fault exists.
设计良好的容错路由算法可以通过在传送数据包时绕过故障来解决NoCs的容错挑战。路由算法不仅应该是容错的,而且应该是无死锁的。哈密顿路径(简称H路径)策略是避免死锁的有力工具。由于H路径在网络中的每个节点恰好经过一次且不包含循环结构,通过沿H路径传输数据包可以轻松防止死锁[7]、[8]、[9]、[10]、[11]、[12]、[13]。近年来,这种优秀的策略被用于设计容错路由算法。例如,HamFA算法[7]是最著名的采用H路径策略的容错路由算法之一。它通过H路径策略构建了两个有向子网,并限制数据包在单个子网中路由,从而避免了死锁。同时,HamFA几乎可以容忍所有单链路故障。FHOE算法[8]也是基于H路径策略的2D NoCs的容错路由算法。它充分结合了传统奇偶转向模型的优点和HamFA策略,因此相比HamFA,可以提供更高的适应性和更多的最短路径选择。考虑到容错的重要性以及H路径在NoCs中的广泛应用,研究NoCs中H路径的存在(即,将H路径嵌入NoCs的问题)是很自然的事情,特别是在故障发生时(即,将H路径嵌入NoCs的容错问题)。然而,众所周知,即使在无故障的情况下,将H路径嵌入网络的问题也是NP完全的。
NoCs usually take interconnection networks as their underlying topology, which inherently affects the performance of NoCs. The k -ary n -cube Qnk is one of the most important interconnection networks for building NoCs owing to its desirable properties, such as regularity, recursive structure, node symmetry, edge symmetry, low-latency, and ease of implementation [14]. The two associated parameters k and n in Qnk provide it the ability to satisfy structural needs in a variety of circumstances. A commercial VLSI chip named the Tours Routing Chip (TRC) was designed early to perform wormhole routing in an arbitrary k -ary n -cube [15]. Furthermore,many fault-tolerant deadlock-free routing algorithms have been developed in Qnk -based NoCs [16], [17],[18]. The desirable properties of Qnk have even attracted a lot of research actually to build data center networks (DCNs), such as CamCube [19], NovaCube [20], CLOT [21], and Wave-Cube [22]. Though the scale of DCNs is much larger than that of NoCs, k -ary n -cubes can easily cope with it. It’s worth pointing out that stronger fault tolerance is necessary for the DCN since it possesses a lot of servers. Moreover, a lot of well-known parallel computing systems like iWarp [23], J-machine [24], Cray T3D [25], Cray T3E [26], and IBM Blue Gene/L [27] all have adopted k -ary n -cubes as their underlying topologies. These Qnk - based architectures usually have high bisection width, high path diversity, high scalability, and affordable implementation cost.
NoCs 通常采用互联网络作为其底层拓扑结构,这本质上影响了 NoCs 的性能。 k -叉 n -立方体 Qnk 是构建 NoCs 的最重要的互联网络之一,这是由于它具有一系列令人期待的特性,如规律性、递归结构、节点对称性、边缘对称性、低延迟和易于实现 [14]。Qnk 中的两个相关参数 kn 使其能够满足各种情况下的结构需求。早期设计的一款商业 VLSI 芯片,名为 Tours 路由芯片(TRC),用于在任意的 k -叉 n -立方体中执行虫洞路由 [15]。此外,基于 Qnk 的 NoCs 已经开发出了许多容错无死锁路由算法 [16]、[17]、[18]。Qnk 的这些理想特性甚至吸引了许多研究实际构建数据中心网络(DCNs),如 CamCube [19]、NovaCube [20]、CLOT [21] 和 Wave-Cube [22]。尽管 DCNs 的规模远大于 NoCs,k -叉 n -立方体可以轻松应对。值得注意的是,由于 DCN 拥有大量服务器,因此它需要更强的容错能力。此外,许多知名的并行计算系统,如 iWarp [23]、J-machine [24]、Cray T3D [25]、Cray T3E [26] 和 IBM Blue Gene/L [27],都采用了 k -叉 n -立方体作为其底层拓扑结构。这些基于 Qnk 的架构通常具有高分割宽度、高路径多样性、高可扩展性和可承受的实现成本。
In order to apply the attractive H-path structure in Qnk with as many faults as possible, the fault-tolerant problem of embedding the H-path into Qnk has been extensively investigated in [28], [29],[30],[31],[32],[33],[34]. A network G is Hamiltonian-connected if an H-path exists between any two nodes in G . Also, G is f -edge fault-tolerant Hamiltonian-connected provided it is Hamiltonian-connected after removing arbitrary f edges in G . Yang et al. [32] proved that for any odd integer k3,Qnk is(2n - 3)-edge fault-tolerant Hamiltonian-connected. Stewart and Xiang [33] proved that for any even integer k4 ,there is an H -path between any two nodes in different partite sets in Qnk with at most 2n2 faulty edges. Yang and Zhang [34] recently showed that for every odd integer k,Qnk admits an H -path between any two nodes that avoids a set F of faulty edges and passes through a set L of prescribed linear forests when |E(L)|+|F|2n3 . All the above results are obtained under the traditional fault model, which doesn't exert any restriction on the distribution of faulty edges. However, Yuan et al. [35] and Xu et al. [36] respectively pointed out that this model has many flaws in the realistic situation since it ignores the fact that it's almost impossible for all faulty nodes (resp. faulty edges) to be adjacent to the same node simultaneously (unless that the node fails). In other words, the fault tolerance assessment approaches under the traditional fault model seriously underestimate the fault tolerance potential of Qnk .
为了尽可能多地应用 Qnk 中的吸引性 H-路径结构,研究者们已经在 [28]、[29]、[30]、[31]、[32]、[33]、[34] 中广泛研究了将 H-路径嵌入 Qnk 的容错问题。一个网络 G 如果任意两个节点之间存在 H-路径,则称为哈密尔顿连通。此外,如果移除 G 中的任意 f 条边后仍然哈密尔顿连通,则 Gf -边容错哈密尔顿连通的。杨等人 [32] 证明了对于任意奇数 k3,Qnk ,它是 (2n - 3)-边容错哈密尔顿连通的。斯图尔特和向 [33] 证明了对于任意偶数 k4 ,在 Qnk 中不同的分部集之间的任意两个节点之间存在一条至多包含 2n2 条故障边的 H -路径。杨和张 [34] 最近表明,对于每个奇数 k,Qnk ,当 |E(L)|+|F|2n3 时,它允许任意两个节点之间存在一条避开故障边集合 F 并通过指定的线性森林集合 LH -路径。以上所有结果都是在传统故障模型下获得的,该模型对故障边的分布没有施加任何限制。然而,袁等人 [35] 和 Xu 等人 [36] 分别指出,由于该模型忽略了几乎不可能所有故障节点(或故障边)同时与同一节点相邻的事实(除非该节点故障),在现实情况下该模型存在许多缺陷。换句话说,传统故障模型下的容错评估方法严重低估了 Qnk 的容错潜力。
The conditional fault model was proposed for tolerating more faulty edges by restricting each node to be adjacent to at least two fault-free edges. Under this model, Wang et al. [29] proved that for any even integer k4 ,there is an H -path between any two nodes in different partite sets in Qnk with at most 4n5 conditional faulty edges. Though the fault tolerance they obtained is about twice that under the traditional fault model, it remains linearly correlated with n . In addition,all the literature mentioned above only provides theoretical proofs about the existence of the H -path in Qnk ,while executable fault-tolerant H -path embedding algorithms and their performance analysis are missing. Thus, this may hinder the practical application of the H -path on Qnk .
条件故障模型被提出,以通过限制每个节点至少与两条无故障边相邻,从而容忍更多的故障边。在这个模型下,王等人 [29] 证明了对于任何偶数 k4,在 Qnk 中,不同分部集的任意两个节点之间存在一条 H 路径,且最多有 4n5 条条件故障边。尽管他们获得的容错能力是传统故障模型下的大约两倍,但它仍然与 n 线性相关。此外,上述所有文献仅提供了关于 QnkH 路径存在的理论证明,而可执行的容错 H 路径嵌入算法及其性能分析却缺失。因此,这可能会阻碍 H 路径在 Qnk 上的实际应用。
In this paper, we pay more attention to the distribution pattern of faulty edges in each dimension of Qnk . This consideration is based on the fact that various dimensions of Qnk usually possess different faulty features in practical fields. For example, to minimize the fabrication cost of TSV links, Qnk -based 3D NoCs are often designed with only partial connection in the vertical dimension (i.e., partial TSVs) [37], [38]. Particularly, the TSV density of 3D NoCs was suggested for only 12.5% in [38]. It implies that only 12.5% of vertical links are available, and 87.5% of vertical links can be deemed faulty. In other words, many missed links exist in one dimension inherently when Qnk is utilized for building 3D NoCs. In this case, we can deem the vertically partially connected NoC topology as a Qnk with many faulty links concentrated at the same dimension.
在本文中,我们更加关注 Qnk 每个维度中故障边的分布模式。这种考虑基于这样一个事实:Qnk 的不同维度在实际领域中通常具有不同的故障特征。例如,为了最小化TSV链路的制造成本,基于 Qnk 的3D NoCs 通常仅在垂直维度(即部分TSV)中设计部分连接 [37]、[38]。特别是,文献 [38] 中建议3D NoC的TSV密度仅为12.5%。这意味着只有12.5%的垂直链路是可用的,而87.5%的垂直链路可以被认为是故障的。换句话说,当使用 Qnk 构建三维NoC时,一个维度中固有无故障链路缺失。在这种情况下,我们可以认为垂直部分连接的NoC拓扑是一个在相同维度上集中了许多故障链路的 Qnk
Based on the above concerns, for a class of networks that exhibit different faulty features in each dimension, we introduce another fault model, named the partitioned edge fault model (PEF model for short), to help such networks achieve a better fault-tolerant capacity. In essence, this model imposes different restrictions on faulty edges in each dimension according to flawed features. In fact, these restrictions are similar to the concept recently proposed by Zhang et al. [39], which pointed out that restricting the number of faulty edges in each dimension is quite important for reflecting the actual fault-tolerant capacity of a network and can be utilized to improve network edge connectivity. Thus, we utilize the PEF model to explore the fault tolerance potential of Qnk when embedding an H-path into Qnk with n2 and odd k3 and evaluate the performance of our approach. Our contributions are presented as follows:
基于以上关切,针对在每一维度展现出不同故障特征的一类网络,我们引入了另一种故障模型,命名为分区边故障模型(简称PEF模型),以帮助这类网络实现更好的故障容忍能力。本质上,该模型根据故障特征对每一维度的故障边施加不同的限制。实际上,这些限制与张等人最近提出的概念相似[39],他们指出限制每一维度中故障边的数量对于反映网络的实际故障容忍能力非常重要,并且可以用来提高网络边连通性。因此,我们利用PEF模型来探索在将H路径嵌入QnkQnk的故障容忍潜力,并评估我们方法的表现。我们的贡献如下所示:
1) We propose a new fault model, the PEF model, to improve the fault tolerance of Qnk when we embed an H-path into the faulty Qnk .
1) 我们提出了一个新的故障模型,PEF模型,以改善在将H路径嵌入故障QnkQnk的故障容忍性。
2) Under the PEF model, we provide a theoretical analysis for proving the existence of the H -path in QnkF ,where F is a PEF set (defined in Section III) such that |F| knk2k12n+5
2) 在PEF模型下,我们提供了理论分析,以证明在QnkF中存在H路径,其中F是一个PEF集合(在第III节中定义),使得|F| knk2k12n+5
3) Based on the obtained theoretical results, we design an O(N) algorithm,named HPPEF ,for embedding the H - path into Qnk under the PEF model,where N is the number of nodes in Qnk . To our knowledge,this is the first time that an algorithm is not only proposed and proved correct, but also actually implemented, for H-path embedding into an edge-faulty Qnk .
3) 基于获得的理论结果,我们设计了一个名为HPPEFO(N)算法,用于在PEF模型下将H路径嵌入Qnk,其中NQnk中的节点数。据我们所知,这是第一次提出并证明正确,且实际实现的算法,用于将H路径嵌入边故障Qnk
The implementation of the algorithm afforded us the ability to observe some features of the generated H -paths. For example,if an edge connecting nodes u and v became faulty,then the path length of u and v in the generated H -path can be an indicator of how important the missed edge is. By experimenting with the algorithm, we gather the data of average path lengths for all edges in the generated H -path.
算法的实现使我们能够观察到生成的 H -路径的一些特征。例如,如果连接节点 uv 的边出现故障,那么在生成的 H -路径中 uv 的路径长度可以作为指示丢失边的重要性的指标。通过实验该算法,我们收集了生成的 H -路径中所有边的平均路径长度数据。
Our algorithm is shown to outperform all known similar works in terms of tolerated faulty-edges. In particular, compared to [32],the improvement is from linear(2n - 3) to exponential knk2k12n+5 . We also show that HP-PEF can support the dynamic degradation of average success rate of constructing required H -paths even when increasing faulty edges exceed knk2k12n+5 .
我们的算法在容忍故障边方面优于所有已知类似工作。特别是,与 [32] 相比,改进是从线性 (2n - 3) 到指数 knk2k12n+5 的。我们还展示了 HP-PEF 可以支持在故障边增加时,构建所需的 H -路径的平均成功率动态降低。
Organization: The rest of this paper is organized as follows. In Section II, we provide the preliminaries used throughout this paper. In Section III, we first present the definition of the PEF model, and then give the theoretical proof related to the existence of the H-path in Qnk under the PEF model. In Section IV,we design the fault-tolerant H-path embedding algorithm HP-PEF based on the theoretical basis in Section III and offer a detailed example for illuminating the execution process of HP-PEF. In Section V, we evaluate the performance of our method by implementing computer programs. Section VI concludes this paper.
组织结构:本文的其余部分组织如下。在第二部分,我们提供了本文中使用的预备知识。在第三部分,我们首先给出了 PEF 模型的定义,然后给出了在 PEF 模型下 Qnk 中 H-路径存在的理论证明。在第四部分,我们基于第三部分的理论基础设计了容错 H-路径嵌入算法 HP-PEF,并给出了一个详细的例子来阐明 HP-PEF 的执行过程。在第五部分,我们通过实现计算机程序来评估我们的方法的性能。第六部分总结本文。

II. Preliminaries
II. 预备知识

A. Terminologies and Notations
A. 术语和符号

For terminologies and notations not defined in this subsection, please refer to the reference [40]. An interconnection network can be modeled as a graph G=(V(G),E(G)) ,where V(G) represents its node set and E(G) represents its edge set. The notations |V(G)| and |E(G)| denote the size of V(G) and E(G) , respectively. Given a graph S ,if V(S)V(G) and E(S) E(G) ,then S is a subgraph of G . Given a node set MV(G) , the subgraph of G induced by M ,denoted by G[M] ,is a graph with the node set M and edge set {(u,v)E(G)u,vM} . Let F be a faulty edge set of G ,and GF be the graph with the node set V(G) and the edge set E(G)F . Given a positive integer n ,we denote the set {1,2,,n} as [n] . Moreover,let Zn=[n1]{0} when n2 and Z1={0} . A graph P= (v0,v1,,vp) is called a path if p+1 nodes v0,v1,,vp are distinct and (vi,vi+1) is an edge of P with iZp . The length of P is the number of the edges in P . If V(P)=V(G) ,then P is a Hamiltonian path (H-path for short) of G .
对于本节未定义的术语和符号,请参考参考文献 [40]。互联网络可以被建模为一个图 G=(V(G),E(G)),其中 V(G) 表示它的节点集合,E(G) 表示它的边集合。|V(G)||E(G)| 分别表示 V(G)E(G) 的大小。给定一个图 S,如果 V(S)V(G)E(S) E(G),那么 SG 的子图。给定一个节点集合 MV(G),由 M 引发的 G 的子图,记作 G[M],是一个具有节点集合 M 和边集合 {(u,v)E(G)u,vM} 的图。设 FG 的故障边集合,GF 为具有节点集合 V(G) 和边集合 E(G)F 的图。给定一个正整数 n,我们记集合 {1,2,,n}[n]。此外,当 Zn=[n1]{0} 时,设 n2Z1={0}。一个图 P= (v0,v1,,vp) 被称为路径,如果 p+1 节点 v0,v1,,vp 是不同的,并且 (vi,vi+1)P 的一条边,且 iZpP 的长度是 P 中的边数。如果 V(P)=V(G),那么 PG 的一条哈密顿路径(简称 H-路径)。

B. k -Ary n -Cube Qnk
B. k -元 n -立方体 Qnk

Definition II.1. (See [33]). The k -ary n -cube Qnk is a graph with the node set V(Qnk)={0,1,,k1}n such that two nodes u=un1un2u0 and v=vn1vn2v0 are adjacent in Qnk if and only if there is an integer iZn satisfying ui=vi±1(modk) and uj=vj for every jZn{i} . In this case,such an edge(u,v)is called an i -dimensional edge for iZn ,and the set of all i -dimensional edges of Qnk is denoted by Ei(Qnk) ,or Ei for short.
定义II.1(见[33])。k -元 n -立方体 Qnk 是一个图,其节点集为 V(Qnk)={0,1,,k1}n,当且仅当存在一个整数 iZn 满足 ui=vi±1(modk)uj=vj 对于每一个 jZn{i} 成立时,两个节点 u=un1un2u0v=vn1vn2v0Qnk 中是相邻的。在这种情况下,这样的边 (u,v) 被称为 i -维边对于 iZn,而 Qnk 的所有 i -维边的集合表示为 Ei(Qnk),简称为 Ei
Hereafter,for brevity,we will omit "(mod k )" in a situation similar to the above definition. By Definition II.1, Qnk is 2n -regular and contains kn nodes. In addition, Qnk is edge symmetric [41]. The Qnk can be partitioned into k disjoint subgraphs Qnk[0],Qnk[1],,Qnk[k1] (abbreviated as Q[0],Q[1],,Q[k1]) along the i -dimension for i Zn . All these k subgraphs are isomorphic to Qn1k . Given a faulty edge set F ,let Fi[l,l+1]={(u,v)uV(Q[l]),v V(Q[l+1])and(u,v)FEi} . If there is no ambiguity, we abbreviate Fi[l,l+1] to F[l,l+1] . Each node of Q[l] has the form u=un1un2ui+1lui1u0 . The node v= un1un2ui+1lui1u0 is the neighbor of u in Q[l] if l=l±1 ,which is denoted by nl(u) . To distinguish the positions of the subgraphs where different nodes are located, let lu=ui=l . That is, lv=lu±1 . Although the values of lu and ui are equal,the notation lu mainly focuses on the position l rather than the dimension i of node u . Let Qnk[,h] (abbreviated as Q[,h] ) be the subgraph induced by node set {uu V(Q[j]) with j=,+1,,h1,h} . Moreover,we have Q[,h]=Q[] when =h ,and taken modulo k ,we have Q[,h]=Qnk when h=1 . A path in Q[,h] is denoted by P,h with V(P,h)V(Q[,h]) . For convenience,we abbreviate P,h to P when =h ,and to P when h=1 by taking modulo k .
此后,为了简洁,我们将在类似于上述定义的情况下省略 "(mod k)"。根据定义II.1,Qnk2n -正则的,并且包含 kn 个节点。此外,Qnk 是边对称的 [41]。Qnk 可以被划分为 k 个不相交的子图 Qnk[0],Qnk[1],,Qnk[k1](简写为 Q[0],Q[1],,Q[k1]) 沿着 i 维度对于 i Zn)。所有这些 k 个子图都与 Qn1k 同构。给定一个故障边集合 F,设 Fi[l,l+1]={(u,v)uV(Q[l]),v V(Q[l+1])and(u,v)FEi}。如果没有歧义,我们简写 Fi[l,l+1]F[l,l+1]Q[l] 的每个节点形式为 u=un1un2ui+1lui1u0。如果 l=l±1,则节点 v= un1un2ui+1lui1u0uQ[l] 中的邻居,表示为 nl(u)。为了区分不同节点所在的子图位置,设 lu=ui=l。即,lv=lu±1。尽管 luui 的值相等,但 lu 的符号主要关注位置 l 而不是节点 u 的维度 i。设 Qnk[,h](简写为 Q[,h])是由节点集 {uu V(Q[j]) 诱导的子图,并带有 j=,+1,,h1,h}。此外,当 =h 时,我们有 Q[,h]=Q[],并且取模 k,当 h=1 时,我们有 Q[,h]=Qnk。在 Q[,h] 中的路径表示为 P,h V(P,h)V(Q[,h])。为了方便,当 =h 时,我们简写 P,hP,当取模 kh=1 时,简写为 P
Fig. 1 shows Q13,Q23 ,and Q33 . We color each edge according to its dimension. In Fig. 1(c),we partition Q33 into 3 disjoint subgraphs Q[0],Q[1] ,and Q[2] along the 2-dimension. The subgraph Q[0,1] is induced by node set {uuV(Q[0]) V(Q[1])} . The node u=110V(Q[1]) is adjacent to two nodes v=010V(Q[0]) and w=210V(Q[2]) . In addition, v=n0(u) and w=n2(u) . It’s easy to see that lv= lu1=0 and lw=lu+1=2 .
图 1 显示了 Q13,Q23Q33 。我们根据边的维度为每条边着色。在图 1(c) 中,我们将 Q33 划分为 3 个不相交的子图 Q[0],Q[1] ,并沿着 2 维进行 Q[2] 。子图 Q[0,1] 由节点集 {uuV(Q[0]) V(Q[1])} 诱导。节点 u=110V(Q[1]) 与两个节点 v=010V(Q[0])w=210V(Q[2]) 相邻。此外,v=n0(u)w=n2(u) 。很容易看出 lv= lu1=0lw=lu+1=2
In particular,the Q2k can be deemed a k×k grid with wraparound edges,where a node ui,j=ij is indexed by its row i and column j . Let p,qZk be two row indices with pq . If p<q ,we define the row torus rt(p,q) to be the subgraph of Q2k induced by the nodes on rows p,p+1,,q ,and particularly, all column edges between nodes on row p and row q are removed when p=0 and q=k1 . Otherwise,if p>q ,we define the row torus rt(p,q) to be the subgraph of Q2k induced by the nodes on rows p,p+1,,k1,0,,q ,and particularly,all column edges between nodes on row p and row q are removed when p=q+1 . Fig. 2 depicts the rt(0,4) ,which is obtained by removing the column edges between nodes on row 0 and row 4 from Q25 . Throughout,we assume that the addition of row or column indices is modulo k .
特别是,Q2k 可以被认为是一个带有环绕边的 k×k 网格,其中节点 ui,j=ij 通过其行 i 和列 j 索引。设 p,qZk 为两个行索引,满足 pq 。如果 p<q ,我们定义行环面 rt(p,q) 为由 Q2k 上的行节点诱导的子图,特别是,当 p=0q=k1 时,移除行 p 和行 q 之间的所有列边。否则,如果 p>q ,我们定义行环面 rt(p,q) 为由 Q2k 上的行节点诱导的子图,特别是,当 p=q+1 时,移除行 p 和行 q 之间的所有列边。图 2 描述了 rt(0,4) ,这是通过从 Q25 中移除行 0 和行 4 之间的列边得到的。在整个过程中,我们假设行或列索引的加法是模 k 的。
Fig. 1. The structures of (a) Q13 ; (b) Q23 ; (c) Q33 .
图 1. (a) Q13 的结构;(b)Q23 的结构;(c)Q33 的结构。
Fig. 2. The structure of rt(0,4) .
图 2. rt(0,4) 的结构。
For the row torus rt(p,q) with qp=1 ,we define the four types of paths in rt(p,q) as follows. The notations of these paths are derived from the shape of their pictorial representations, where i¯=q+pi .
对于具有 qp=1 的行环面 rt(p,q),我们定义 rt(p,q) 中的四种路径如下。这些路径的表示法来源于它们图形表示的形状,其中 i¯=q+pi
N+(ui,j,ui,j)=(ui,j,ui¯,j,ui¯,j+1,ui,j+1,ui,j+2,ui¯,j+2,
ui¯,j+3,ui,j+3,ui,j+4,,ui,j1,ui,j)
wherei{p,q},0jjk1,
and|jj|is even.
N(ui,j,ui,j)=(ui,j,ui¯,j,ui¯,j1,ui,j1,ui,j2,ui¯,j2,
ui¯,j3,ui,j3,ui,j4,,ui,j+1,ui,j)
wherei{p,q},0jjk1,
and|jj|is even.
Cm+(ui,j,ui¯,j)=(ui,j,ui,j+1,ui,j+2,,ui,m1,ui,m,
ui¯,m,ui¯,m1,ui¯,m2,,ui¯,j+1,ui¯,j)
wherei{p,q},0jk1,and
0mk1
Cm(ui,j,ui,j)=(ui,j,ui,j1,ui,j2,,ui,m+1,ui,m,
ui¯,m,ui¯,m+1,ui¯,m+2,,ui¯,j1,ui¯,j)
wherei{p,q},0jk1,and
0mk1
In particular,if m=j ,then Cm+(ui,j,ui¯,j)= Cm(ui,j,ui¯,j)=(ui,j,ui¯,j).
特别地,如果 m=j,那么 Cm+(ui,j,ui¯,j)= Cm(ui,j,ui¯,j)=(ui,j,ui¯,j).

III. THEORETICAL BASIS FOR EMBEDDING THE HAMILTONIAN PATH INTO k -ARY n -CUBES
III. 将 Hamiltonian 路径嵌入 kn 立方体的理论依据

In this section, we establish the theoretical basis for embedding the H-path into k -ary n -cubes under the PEF model. That is,we will prove that an H -path can be found in a k -ary n -cube Qnk in the presence of a partitioned edge fault set,described below.
在这一节中,我们建立了在PEF模型下将H路径嵌入 kn 立方体的理论依据。也就是说,我们将证明在存在如下描述的分隔边故障集的情况下,可以在 kn 立方体 Qnk 中找到一个 H 路径。
Let F be a faulty edge set in Qnk ,and let Fi=FEi with iZn . We set {e0,e1,,en1}={|Fi|iZn} such that en1en2e0 . The faulty edge set F is a partitioned edge fault set (PEF set for short) if and only if eif(i)< |E(Qnk)|n=kn for each iZn ,where f(i) is a function of i or a fixed value.
FQnk 中的一个故障边集,且设 Fi=FEi 满足 iZn。我们设定 {e0,e1,,en1}={|Fi|iZn} 使得 en1en2e0。故障边集 F 是一个分隔边故障集(简称为PEF集),当且仅当对于每个 iZn,都有 eif(i)< |E(Qnk)|n=kn,其中 f(i)i 的函数或一个固定值。
For a PEF set FE(Qnk) ,since Qnk is recursively constructed with edge symmetry, we can utilize the inductive method to analyze the Hamiltonian property of Qnk by partitioning it into k subgraphs along a dimension we expected. Consequently,provided that QnkF is Hamiltonian-connected, the exact values of f(i) can be derived by analyzing the number of faulty edges that can be tolerated when the H-path passes through two consecutive subgraphs.
对于一个PEF集合 FE(Qnk) ,由于 Qnk 是通过边对称递归构造的,我们可以利用归纳法通过沿预期维度的 k 子图划分来分析 Qnk 的哈密顿性质。因此,如果 QnkF 是哈密顿连通的,那么通过分析当哈密顿路径经过两个连续子图时可以容忍的故障边数,可以推导出 f(i) 的确切值。
The following result is provided for dealing with the base case of our forthcoming inductive proof.
下面给出的结果是用来处理我们即将进行的归纳证明的基例。
Lemma III.1. (See [42]) For odd k3 ,let FE(Q2k) with |F|1 . Then Q2kF is Hamiltonian-connected.
引理III.1。(见[42])对于奇数 k3 ,设 FE(Q2k) 满足 |F|1 。那么 Q2kF 是哈密顿连通的。
Theorem III.2. For n2 and odd k3 ,let FE(Qnk) be a PEF set satisfying the following conditions:
定理III.2。对于 n2 和奇数 k3 ,设 FE(Qnk) 是一个满足以下条件的PEF集合:
1) |F|knk2k12n+5 ;
2) eiki2 for each iZnZ2 ;
2) eiki2 对于每个 iZnZ2
3) e0=0 and e11 .
3) e0=0e11
Then, QnkF is Hamiltonian-connected.
那么, QnkF 是哈密顿连通的。
Proof. The proof is by induction on n . When n=2 ,by Lemma III.1,the theorem holds obviously. For n3 ,assume this theorem holds for all Qmk ’s with m<n . Therefore,what we need to prove is that this theorem holds for Qnk .
证明。证明采用对 n 的归纳法。当 n=2 时,由引理III.1可知,定理显然成立。对于 n3 ,假设定理对于所有 Qmkm<n 成立。因此,我们需要证明的是定理对于 Qnk 也成立。
Since Qnk is edge symmetric,without loss of generality, let |Fn1|=max{|Fn1|,|Fn2|,,|F0|} . That is, |Fn1|= en1kn12 . Along the(n - 1)-dimension,we divide Qnk into k disjoint subgraphs Q[0],Q[1],,Q[k1] ,all of which are isomorphic to Qn1k . Let s and t be arbitrary two vertices of Qnk with sV(Q[ls]) and tV(Q[lt]) . By the arbitrariness of s and t ,suppose that lslt .
由于 Qnk 是边缘对称的,不失一般性,设 |Fn1|=max{|Fn1|,|Fn2|,,|F0|} 。即 |Fn1|= en1kn12 。在 (n - 1) 维上,我们将 Qnk 分成 k 个不相交的子图 Q[0],Q[1],,Q[k1] ,它们都与 Qn1k 同构。设 stQnk 中任意两个顶点,满足 sV(Q[ls])tV(Q[lt]) 。由于 st 的任意性,假设 lslt
Let Chl=E(Q[l])Fh with lZk and hZn1 . Moreover,for each lZk ,let {en2l,en3l,,e0l}= {|Cn2l|,|Cn3l|,,|C0l|} such that en2len3le0l . According to the recursive nature and conditions 2) and 3), when n=3 ,we have |F||Fn1|=i=01|Fi|1,e0l=0 , and e1l1 . When n4 ,we have
Chl=E(Q[l])Fh 满足 lZkhZn1 。此外,对于每个 lZk ,设 {en2l,en3l,,e0l}= {|Cn2l|,|Cn3l|,,|C0l|} 使得 en2len3le0l 。根据递归性质以及条件 2) 和 3),当 n=3 时,我们有 |F||Fn1|=i=01|Fi|1,e0l=0 ,以及 e1l1 。当 n4 时,我们有
|F||Fn1|=i=0n2|Fi|=i=2n2ei+i=01ei
i=2n2(ki2)+1
=kn1k2k12(n1)+5.
In addition, e0l=0,e1l1 ,and eilki2 for each iZn1Z2 . Therefore,every Q[l]F with lZk is Hamiltonian-connected. That is,when ls=lt ,there exists an H -path in Q[ls]F between s and t .
此外,e0l=0,e1l1 ,且对于每个 iZn1Z2eilki2 。因此,每个 Q[l]FlZk 的图都是哈密顿连通的。即,当 ls=lt 时,在 Q[ls]F 中存在一条连接 stH -路径。
Without loss of generality,suppose that |F[k1,0]|= max{|F[0,1]|,,|F[k2,k1]|,|F[k1,0]|}. Since l=0k1|F[l,l+1]|=|Fn1|kn12 and k3 is odd, |F[l,l+1]|kn122=kn132 for all lZk1 .
不失一般性,假设 |F[k1,0]|= max{|F[0,1]|,,|F[k2,k1]|,|F[k1,0]|}. 。由于 l=0k1|F[l,l+1]|=|Fn1|kn12k3 是奇数,因此 |F[l,l+1]|kn122=kn132 对所有 lZk1 成立。
Claim 1: Suppose that there exists an H -path Pq in Q[q]F between any two distinct nodes in Q[q] . When 0qk
引理 1:假设在 Q[q] 中任意两个不同节点之间存在一条 H -路径 Pq 。当 0qk
Fig. 3. The constructions in Case 1.1 of Theorem III.2.
图 3。定理 III.2 中情形 1.1 的构造。
2,there exists at least one edge (x,x)E(Pq) such that (x,nq+1(x)),(x,nq+1(x))Fn1 . And when 1qk 1,there exists at least one edge (x,x)E(Pq) such that (x,nq1(x)),(x,nq1(x))Fn1 .
存在至少一条边 (x,x)E(Pq) 使得 (x,nq+1(x)),(x,nq+1(x))Fn1 。当 1qk 1时,存在至少一条边 (x,x)E(Pq) 使得 (x,nq1(x)),(x,nq1(x))Fn1
The length of Pq is kn11 . Then there exist kn112 mutually disjoint edges on Pq . When 0qk2 ,since kn112 |F[q,q+1]|1 ,there exists at least one edge (x,x)E(Pq) such that (x,nq+1(x)),(x,nq+1(x))Fn1 . Analogously, when 1qk1 ,we can also find at least one edge (x,x) E(Pq) such that (x,nq1(x)),(x,nq1(x))Fn1 . Then the claim holds.
Pq 的长度是 kn11 。然后在 Pq 上存在 kn112 条互不相交的边。当 0qk2 时,由于 kn112 |F[q,q+1]|1 ,存在至少一条边 (x,x)E(Pq) 使得 (x,nq+1(x)),(x,nq+1(x))Fn1 。类似地,当 1qk1 时,我们也可以找到至少一条边 (x,x) E(Pq) 使得 (x,nq1(x)),(x,nq1(x))Fn1 。那么,该命题成立。
Next, we discuss the following cases separately.
接下来,我们分别讨论以下情况。
Case 1: ls=0 .
情况1:ls=0
Case 1.1: ls=lt .
情况1.1:ls=lt
Since Q[0]F is Hamiltonian-connected,there exists an H-path P0 in Q[0]F between s and t . By Claim 1,there exists at least one edge (x,x) of P0 such that (x,n1(x)),(x,n1(x))Fn1 . Similarly,since Q[1]F is Hamiltonian-connected,there exists an H -path P1 in Q[1]F between n1(x) and n1(x) . By Claim 1,there exists at least one edge (y,y) of P1 such that (y,n2(y)),(y,n2(y))Fn1 . By constantly iterating in this way, we can obtain an H-path P2,k1 in Q[2,k1]F between n2(y) and n2(y) . Thus, P0P1P2,k1{(x,n1(x)),(n1(x),x) , (y,n2(y)),(n2(y),y)}{(x,x),(y,y)} forms the required H-path between s and t in QnkF (see Fig. 3).
由于 Q[0]F 是哈密顿连通的,存在一条从 st 的 H-路径 P0Q[0]F 中。根据命题1,存在 P0 中的至少一条边 (x,x) 使得 (x,n1(x)),(x,n1(x))Fn1 。类似地,由于 Q[1]F 是哈密顿连通的,存在一条从 n1(x)n1(x)H -路径 P1Q[1]F 中。根据命题1,存在 P1 中的至少一条边 (y,y) 使得 (y,n2(y)),(y,n2(y))Fn1 。通过这种方式不断迭代,我们可以得到一条从 n2(y)n2(y) 的 H-路径 P2,k1Q[2,k1]F 中。因此,P0P1P2,k1{(x,n1(x)),(n1(x),x)(y,n2(y)),(n2(y),y)}{(x,x),(y,y)} 构成了在 QnkF 中从 st 所需的 H-路径(见图3)。
Case 1.2: lslt .
情况1.2:lslt
Since |V(Q[0])||{s,t}||F[0,1]|kn12 kn132>1 with n3 and odd k3 ,there exists one node xV(Q[0]) such that xs,n1(x)t ,and (x,n1(x))Fn1 . Since Q[0]F is Hamiltonian-connected, there exists an H -path P0 in Q[0]F between s and x . If lt=1 ,since Q[1]F is Hamiltonian-connected,there exists an H -path P1 in Q[1]F between n1(x) and t ; otherwise, if 2ltk1 ,proceeding iteratively in this manner can construct an H -path P1,lt in Q[1,lt]F between n1(x) and t . If lt=k1 ,then P0P1,lt{(x,n1(x))} forms the required H-path between s and t in QnkF ; otherwise,by Claim 1, there exists one edge (y,y)E(P1,lt)E(Q[lt]) such that (y,nlt+1(y)),(y,nlt+1(y))Fn1 . Similar to Case 1.1, we can construct an H-path Plt+1,k1 in Q[lt+1,k1]F between nlt+1(y) and nlt+1(y) . Therefore, P0P1,lt Plt+1,k1{(x,n1(x)),(y,nlt+1(y)),(nlt+1(y),y)} {(y,y)} forms the required H -path between s and t in QnkF (see Fig. 4).
由于 |V(Q[0])||{s,t}||F[0,1]|kn12 kn132>1 具有 n3 并且是奇数 k3,存在一个节点 xV(Q[0]) 使得 xs,n1(x)t,并且 (x,n1(x))Fn1。由于 Q[0]F 是哈密顿连通的,存在一个 H -路径 P0Q[0]F 中介于 sx 之间。如果 lt=1,由于 Q[1]F 是哈密顿连通的,存在一个 H -路径 P1Q[1]F 中介于 n1(x)t 之间;否则,如果 2ltk1,以这种方式迭代进行可以构造一个 H -路径 P1,ltQ[1,lt]F 中介于 n1(x)t 之间。如果 lt=k1,那么 P0P1,lt{(x,n1(x))} 形成了在 QnkF 中介于 st 之间的所需的 H-路径;否则,根据引理1,存在一条边 (y,y)E(P1,lt)E(Q[lt]) 使得 (y,nlt+1(y)),(y,nlt+1(y))Fn1。类似于情况1.1,我们可以构造一个 H-路径 Plt+1,k1Q[lt+1,k1]F 中介于 nlt+1(y)nlt+1(y) 之间。因此,P0P1,lt Plt+1,k1{(x,n1(x)),(y,nlt+1(y)),(nlt+1(y),y)} {(y,y)} 形成了在 QnkF 中介于 st 之间的所需的 H -路径(见图4)。
Fig. 4. The constructions in Case 1.2 of Theorem III.2.
图4。定理III.2中情况1.2的构造。
Case 2: ls1 .
情况2:ls1
When lt=k1 ,we can construct the required H -path similar to Case 1. Then we discuss the case of 1lsltk2 .
lt=k1 时,我们可以类似于情况1构造所需的 H -路径。然后我们讨论 1lsltk2 的情况。
Similar to Case 1,we can construct an H-path Pls,k1 in Q[ls,k1]F between s and t . If the part of Pls,k1 in Q[ls] is constructed by the method similar to Case 1.1,by the proof of Case 1.1,let (w,w) be the edge in Q[ls] satisfying {(w,nls+1(w)),(w,nls+1(w))}E(Pls,k1) . By Claim 1,there exists one edge (x,x)E(Pls,k1)E(Q[ls]) (or (x,x)(E(Pls,k1)E(Q[ls])){(w,w)} if (w,w) exists) and (x,nls1(x)),(x,nls1(x))Fn1 . Similar to Case 1.1,we can construct an H-path P0,ls1 in Q[0,ls1]F between nls1(x) and nls1(x) . If (x,x)E(Pls,k1)E(Q[ls]), then Pls,k1P0,ls1 {(x,nls1(x)),(nls1(x),x)}{(x,x)} forms the required H -path between s and t in QnkF .
与案例1类似,我们可以在 Pls,k1 中构造一个 H-路径 Q[ls,k1]F ,连接 st 。如果 Pls,k1Q[ls] 中的部分是通过类似于案例1.1的方法构造的,根据案例1.1的证明,设 (w,w) 是满足 {(w,nls+1(w)),(w,nls+1(w))}E(Pls,k1)Q[ls] 中的边。根据命题1,存在一个边 (x,x)E(Pls,k1)E(Q[ls]) (如果存在 (w,w) ,则为 (x,x)(E(Pls,k1)E(Q[ls])){(w,w)})和 (x,nls1(x)),(x,nls1(x))Fn1 。类似于案例1.1,我们可以在 Q[0,ls1]F 中构造一个 H-路径 P0,ls1 ,连接 nls1(x)nls1(x) 。如果 (x,x)E(Pls,k1)E(Q[ls]), ,那么 Pls,k1P0,ls1 {(x,nls1(x)),(nls1(x),x)}{(x,x)} 形成所需的 H -路径,连接 stQnkF 中。
Otherwise,we have (x,x)=(w,w) and thus {(x,nls+1(x)),(x,nls+1(x))}E(Pls,k1) . In this situation,the H -path Pls,k1 must be constructed by the manner in Case 1.1. It implies that ls=lt and there exists an H-path Pls in Q[ls]F between s and t ,which passes through the edge (x,x) . If |F[ls,ls+1]|=kn132 ,then
否则,我们有 (x,x)=(w,w) ,因此 {(x,nls+1(x)),(x,nls+1(x))}E(Pls,k1) 。在这种情况下,H -路径 Pls,k1 必须以案例1.1中的方式构造。这意味着 ls=lt ,并且存在一个 H-路径 PlsQ[ls]F 中,连接 st ,该路径通过边 (x,x) 。如果 |F[ls,ls+1]|=kn132 ,那么
|F[ls1,ls]|kn12(|F[ls,ls+1]|
+|F[k1,0]|)
kn122×kn1321.
Since kn112|F[ls1,ls]|>2 with n3 and odd k 3,there exists one edge (y,y)E(Pls) such that (y,y) (x,x) and (y,nls1(y)),(y,nls1(y))Fn1 . Otherwise, if |F[ls,ls+1]|kn152 ,since kn112|F[ls,ls+1]|2 , then there exists at least one edge (y,y)E(Pls) such that (y,y)(x,x) and (y,nls+1(y)),(y,nls+1(y))Fn1 . Thus,there exists at least one edge (y,y)E(Pls) such that (y,y)(x,x) and (y,nls+1(y)),(y,nls+1(y))Fn1 or (y,nls1(y)),(y,nls1(y))Fn1 .
由于 kn112|F[ls1,ls]|>2n3 和奇数 k 3,存在一个边 (y,y)E(Pls) 使得 (y,y) (x,x)(y,nls1(y)),(y,nls1(y))Fn1 。否则,如果 |F[ls,ls+1]|kn152 ,由于 kn112|F[ls,ls+1]|2 ,那么存在至少一个边 (y,y)E(Pls) 使得 (y,y)(x,x)(y,nls+1(y)),(y,nls+1(y))Fn1 。因此,存在至少一个边 (y,y)E(Pls) 使得 (y,y)(x,x)(y,nls+1(y)),(y,nls+1(y))Fn1 或者 (y,nls1(y)),(y,nls1(y))Fn1
Note that the four edges (x,nls1(x)),(x,nls1(x)) , (x,nls+1(x)),(x,nls+1(x))Fn1 . If (y,nls+1(y)),(y , nls+1(y))Fn1 ,by Case 1.1,we can construct an H-path Pls+1,k1 in Q[ls+1,k1]F between nls+1(y) and nls+1(y) . Similar to Case 1.1,we can construct an H-path P0,ls1 in Q[0,ls1]F between nls1(x) and nls1(x) . Then PlsP0,ls1Pls+1,k1 {(x,nls1(x)),(nls1(x),x),(y,nls+1(y)),(nls+1(y),y)} {(x,x),(y,y)} forms the required H -path between s and t in QnkF . If (y,nls1(y)),(y,nls1(y))Fn1 ,by Case 1.1,we can construct an H -path P0,ls1 in Q[0,ls1]F between nls1(y) and nls1(y) . Similar to Case 1.1,we construct an H-path Pls+1,k1 in Q[ls+1,k1]F between nls+1(x) and nls+1(x) . Then PlsP0,ls1Pls+1,k1 {(y,nls1(y)),(nls1(y),y),(x,nls+1(x)),(nls+1(x),x)} {(x,x),(y,y)} forms the required H -path between s and t in QnkF (see Fig. 5).
注意四个边缘 (x,nls1(x)),(x,nls1(x)) ,(x,nls+1(x)),(x,nls+1(x))Fn1 。如果 (y,nls+1(y)),(y ,nls+1(y))Fn1 ,根据情况1.1,我们可以在 Q[ls+1,k1]F 中构造一个从 nls+1(y)nls+1(y) 的 H-路径 Pls+1,k1 。类似于情况1.1,我们可以在 Q[0,ls1]F 中构造一个从 nls1(x)nls1(x) 的 H-路径 P0,ls1 。那么 PlsP0,ls1Pls+1,k1 {(x,nls1(x)),(nls1(x),x),(y,nls+1(y)),(nls+1(y),y)} {(x,x),(y,y)} 形成了所需的 H -路径,从 stQnkF 中。如果 (y,nls1(y)),(y,nls1(y))Fn1 ,根据情况1.1,我们可以在 Q[0,ls1]F 中构造一个从 nls1(y)nls1(y)H -路径 P0,ls1 。类似于情况1.1,我们构造一个从 nls+1(x)nls+1(x) 的 H-路径 Pls+1,k1Q[ls+1,k1]F 中。那么 PlsP0,ls1Pls+1,k1 {(y,nls1(y)),(nls1(y),y),(x,nls+1(x)),(nls+1(x),x)} {(x,x),(y,y)} 形成了所需的 H -路径,从 stQnkF 中(见图5)。
Fig. 5. The constructions in Case 2 of Theorem III.2.
图5。定理III.2中情况2的构造。

IV. FAULT-TOLERANT HAMILTONIAN PATH EMBEDDING ALGORITHM OF k -ARY n -CUBES
IV. k -元 n -立方体的容错哈密顿路径嵌入算法

In this section,we present the fault-tolerant H -path embedding algorithm for Qnk under the PEF model.
在本节中,我们提出了在PEF模型下的 H -路径的容错嵌入算法,适用于 Qnk
First,we design Algorithm 1 costing O(k2) time to construct the H -path in Q2kF according to the theoretical proof in [42], where Procedure HP-rtFree is utilized to find the H-path in a fault-free rt(p,q) . In Algorithm 1,we let s=ua,b and t=uc,d be two arbitrary distinct nodes in rt(p,q) . In addition,without loss of generality,suppose that ac . Given an edge fault set FE(Q2k) with |F|1 ,by the symmetry of Q2k ,suppose that (u0,0,u0,1) is the faulty edge if it exists.
首先,我们设计算法1,该算法花费 O(k2) 时间来根据 [42] 中的理论证明在 Q2kF 中构建 H -路径,其中使用了过程 HP-rtFree 来在无故障的 rt(p,q) 中查找 H-路径。在算法1中,我们让 s=ua,bt=uc,d 成为 rt(p,q) 中的两个任意不同节点。此外,不失一般性,假设 ac 。给定一个边缘故障集 FE(Q2k) ,其中包含 |F|1 ,由于 Q2k 的对称性,假设 (u0,0,u0,1) 是存在故障的边缘。
Based on Algorithm 1, we design the Algorithm HP-PEF under the PEF model. Note that the Algorithm HP-PEF is essentially based on the theoretical basis in Section III, where Procedures HP-Round and HP-Direct correspond to the constructive approaches of Case 1.1 and Case 1.2 in Theorem III.2, respectively. In addition, the fault tolerance of Algorithm HP-PEF has been determined by Theorem III.2 (i.e., the three conditions shown in Theorem III.2).
基于 Algorithm 1,我们设计了在 PEF 模型下的 Algorithm HP-PEF。注意 Algorithm HP-PEF 实质上基于第 III 节中的理论依据,其中过程 HP-Round 和 HP-Direct 分别对应定理 III.2 中的案例 1.1 和案例 1.2 的构造方法。此外,Algorithm HP-PEF 的容错性已经由定理 III.2 确定(即定理 III.2 中显示的三个条件)。
Theorem IV.1. For n2 and odd k3 ,the algorithm HP-PEF can embed an H-path between arbitrary two nodes s and t into QnkF ,where F is a PEF set satisfying (1) |F|knk2k1 2n+5 ; (2) eiki2 for each iZnZ2 ; (3) e0=0 and e11 .
定理 IV.1。对于 n2 和奇数 k3 ,算法 HP-PEF 可以在任意两个节点 st 之间嵌入一个 H-路径到 QnkF 中,其中 F 是满足以下条件的 PEF 集合:(1)|F|knk2k1 2n+5;(2)对于每个 iZnZ2eiki2;(3)e0=0e11
Proof. We prove this theorem by induction on n . When n=2 , HP-PEF calls Algorithm 1 to embed the required H-path into Q2kF ,where F is a PEF set satisfying e0=0 and e11 . Assume this theorem holds for all Qmk ’s with m<n . Then we need to prove that this theorem holds for Qnk .
证明。我们通过对 n 进行归纳来证明这个定理。当 n=2 时,HP-PEF 调用算法 1 将所需的 H-路径嵌入到 Q2kF 中,其中 F 是满足 e0=0e11 的 PEF 集合。假设这个定理对于所有 Qmkm<n 都成立。那么我们需要证明这个定理对于 Qnk 也成立。
Algorithm 1: Embed an H-path P into Q2kF .
算法 1:将 H-路径 P 嵌入到 Q2kF 中。

Input: A k -ary 2-cube Q2k with odd k3 ,an edge fault
set F with |F|1 ,two distinct nodes s=ua,b
and t=uc,d .
Output: An H-path P in Q2kF between s and t .
P ;
if k=3 then Implement an exhaustive search;
else
if there exists no faulty edge then
Call HP-rtFree (rt(0,k1),s,t) ;
else
if {a,c}={0,1} then
Construct two disjoint paths avoiding the
edge (u0,0,u0,1),P from s to s and P
from t to t in rt(0,1) such that V(P)
V(P)=V(rt(0,1)) ;
Let s (resp. t ) be the neighbor of s (resp.
t) in Q2krt(0,1) ;
Call HP-rtFree (rt(2,k1),s,t) ;
PPPP{(s,s),(t,t)};
else if {a,c}{2,3,,k1} then
CC0+(u0,1,u1,1){(u1,1,u0,1)}
Call HP-rtFree (rt(2,k1),s,t) ;
Merge C into P through an edge of P on
row 2,which isn’t (u2,0,u2,1) ;
else
Let P be the H -path avoiding the edge
(u0,0,u0,1) in rt(0,1) which begins at s and
ends at s that isn’t adjacent to t ;
Let t be the neighbor of s in Q2krt(0,1) ;
Call HP-rtFree (rt(2,k1),t,t) ;
PPP{(s,t)}
return P ;

In Lines 4-5,HP-PEF divides Qnk into k disjoint subgraphs Q[0],Q[1],,Q[k1] along the i -dimension such that |Fi|=en1kn12 . Given an integer lZk ,let {en2,en3,,e0}={|FjE(Q[l])|jZn{i}} such that en2en3e0 . Then similar to the proof of Theorem III.2,for each lZk,FE(Q[l]) is a PEF set satisfying (1) |FE(Q[l])|kn1k2k12(n1)+5 ; (2) eiki2 for each iZn1Z2;(3)e0=0 and e11 . By the induction hypothesis, HP-PEF can embed an H-path between arbitrary two nodes into Q[l]FE(Q[l]) . Next,in Line 6,let l denote the position of the subgraph which connects to the largest number of i -dimensional faulty edges. The subsequent constructive process prohibits the use of the edges between Q[l] and Q[l+1] (see the cross sign in Fig. 6). In Lines 7-10,if the node s (resp. t) is closer to Q[l] along the clockwise (see the green lines in Fig. 6) than t (resp. s ),HP-PEF takes s (resp. t ) as the source node a . Correspondingly,the node t (resp. s ) is deemed as the destination node b .
在第4-5行中,HP-PEF将 Qnk 分解为 k 沿着 i 维的 Q[0],Q[1],,Q[k1] 不相交子图,使得 |Fi|=en1kn12 。给定一个整数 lZk ,设 {en2,en3,,e0}={|FjE(Q[l])|jZn{i}} 使得 en2en3e0 。然后类似于定理III.2的证明,对于每个 lZk,FE(Q[l]) 是一个满足(1)|FE(Q[l])|kn1k2k12(n1)+5;(2)对于每个 iZn1Z2;(3)e0=0e11 的PEF集合。根据归纳假设,HP-PEF可以在 Q[l]FE(Q[l]) 之间嵌入任意两个节点之间的H路径。接下来,在第6行中,设 l 表示连接到最大数量的 i 维故障边的子图的位置(见图6中的交叉符号)。在第7-10行中,如果节点 s(分别地 t) 沿着顺时针方向(见图6中的绿色线条)比 t(分别地 s )更接近 Q[l] ,HP-PEF将 s(分别地 t )作为源节点 a 。相应地,节点 t(分别地 s )被视为目标节点 b
In Lines 11-20, HP-PEF embeds the required H-path into QnkF by discussing three situations similar to Theorem III.2. In the constructive process,we let l denote the destination subgraph,and d denote the constructive direction. More specifically, d=1 (resp. d=1 ) means the constructive process will proceed along the clockwise (resp. counterclockwise). Theorem III. 2 provides a detailed proof related to the correctness of Lines 11-20 when i=n1,l=k1,a=s ,and b=t . Though l,a ,and b may change in each iteration,their relative positions remain unchanged, and the construction process is similar in different cases. Thus, the theorem holds.
在第11-20行中,HP-PEF通过讨论类似于定理III.2的三个情况,将所需的H路径嵌入到 QnkF 中。在构造过程中,我们让 l 表示目标子图,d 表示构造方向。更具体地说,d=1(分别d=1)意味着构造过程将沿顺时针(分别逆时针)方向进行。定理III.2提供了与 i=n1,l=k1,a=sb=t 时第11-20行正确性相关的详细证明。尽管 l,ab 在每次迭代中可能发生变化,但它们的相对位置保持不变,且在不同情况下构造过程相似。因此,该定理成立。
Procedure: HPrtFree(rt(p,q),s,t) .
过程:HPrtFree(rt(p,q),s,t)
begin
开始

if qp=1 then
if a=c and db(modk) is odd then
PN+(s,ua,d1)Cb1+(ua¯,d,t)
{(ua,d1,ua¯,d1,ua¯,d)} ;
else if a=c and db(modk) is even then
PCd1+(s,ua¯,b)N(ua¯,b1,ua¯,d)
{(ua¯,b,ua¯,b1),(ua¯,d,t)} ;
else if ac and db(modk) is odd then
PN(s,ua,d)Cb+1(ua,d,t);
else if ac and db(modk) is even then
PCd+1(s,ua¯,b)
if bd then PPN+(ua¯,b+1,ua¯,d1)
{(ua¯,b,ua¯,b+1),(ua¯,d1,ua,d1,ua,d,t)};
else
if a=p and c=q then
Call HP-rtFree (rt(p,q1),s,uc1,d1) ;
PP{(uc1,d1,uc,d1,uc,d2,,
uc,d+1,t)} ;
else
Without loss of generality, suppose that
s,tV(rt(p,q1)) ;
Call HP-rtFree (rt(p,q1),s,t) ;
Choose an edge (uq1,h,uq1,h+1) of P on
row q1 ;
PP{(uq1,h,uq,h,uq,h1,,uq,h+2,
uq,h+1,uq1,h+1)}{(uq1,h,uq1,h+1)};

Fig. 6. The relative positions of l and nodes a and b .
图6。l与节点 ab 的相对位置。
Algorithm 2: Embed an H-path P into QnkF where F is a PEF set (HP-PEF).
算法2:将H路径 P 嵌入到 QnkF 中,其中 F 是PEF集合(HP-PEF)。

Input: A k -ary n -cube Qnk with n2 and odd k3 ,
two distinct nodes s and t ,a PEF set F satisfying
(1) |F|knk2k12n+5 ; (2) eiki2 for each
iZnZ2 ; (3) e0=0 and e11 .
Output: An H-path P in QnkF between s and t .
P ;
if n=2 then PAlgorithm1(Q2k,F,s,t) ;
else
iargmaxiZn{|Fi|}
Divide Qnk into k disjoint subgraphs Q[0],Q[1] ,
,Q[k1] along the i -dimension;
largmaxlZk{|Fi[l,(l+1)modk]|};
// Take a (resp. b ) as the source node (resp.
destination node).
if lsl(modk)ltl(modk) then
as;bt;
else at;bs ;
if la=l+1(modk) then // Situation 1
if la=lb then Call HP-Round (l,1,a,b) ;
else Call HP-Direct (l,1,a,b) ;
else if la=l then // Situation 2
Call HP-Direct (l+1,1,a,b) ;
else // Situation 3
Call HP-Direct (l,1,a,b) ;
Select an edge (x,x)E(P)E(Q[la]) such
that (x,nla1(x)),(x,nla1(x))Fi ;
Call HP-Round (l+1,1,nla1(x),nla1(x)) ;
PP{(x,nla1(x)),(nla1(x),x)}
{(x,x)} ;
return P ;

Procedure: HP-Round(l,d,s,t).
过程:HP-Round(l,d,s,t)。

begin
us;vt ;
// Take l as the destination subgraph,and d as the
constructive direction.
if lls then
for 1 to d×(lls)modk do
P Algorithm 2(Q[lu],FE(Q[lu]),u,v) ;
Select an edge (x,x)E(P) such that
(x,nlu+d(x)),(x,nlu+d(x))Fi;
PPP{(x,nlu+d(x)),(nlu+d(x),x)}
{(x,x)} ;
unlu+d(x);vnlu+d(x);
P Algorithm 2(Q[lu],FE(Q[lu]),u,v) ;
PPP;

The time complexity of HP-PEF is showed as follows.
HP-PEF的时间复杂度如下所示。
Theorem IV.2. The time complexity of HP-PEF is O(N) , where N=kn .
定理IV.2。HP-PEF的时间复杂度是 O(N) ,其中 N=kn
Proof. When n=2 ,HP-PEF calls Algorithm 1,which costs O(k2) time. Next,we discuss the case of n3 in the following.
证明。当 n=2 时,HP-PEF调用算法1,其花费 O(k2) 时间。接下来,我们讨论 n3 的情况。
Since HP-PEF calls HP-Round and HP-Direct frequently, we first analyse the time complexity of HP-Round and HP-Direct.
由于HP-PEF频繁调用HP-Round和HP-Direct,我们首先分析HP-Round和HP-Direct的时间复杂度。
Procedure: HP-Direct(l,d,s,t) .
过程:HP-Direct(l,d,s,t)

begin
us ;
// Take l as the destination subgraph,and d as the
constructive direction.
if ltls then
for 1 to d×(ltls)modk do
Select a node xV(Q[lu]) with xu ,
nlu+d(x)t ,and (x,nlu+d(x))Fi ;
P Algorithm 2(Q[lu],FE(Q[lu]),u,x) ;
PPP{(x,nlu+d(x))};
unlu+d(x);
P Algorithm 2(Q[lu],FE(Q[lu]),u,t) ;
PPP;
if ltl then
Select an edge (x,x)E(P)E(Q[lt]) such
that (x,nlt+d(x)),(x,nlt+d(x))Fi ;
Call HP-Round (l,d,nlt+d(x),nlt+d(x)) ;
PP{(x,nlt+d(x)),(nlt+d(x),x)}
{(x,x)} ;

The main time costs of HP-Round and HP-Direct are on the for-loops. The for-loops execute at most k iterations. Each iteration calls HP-PEF and selects a required edge or node. Calling HP-PEF to construct the H-path in every subgraph of Qnk requires kn3O(k2)=O(kn1) . The H-path obtained contains kn112 mutually disjoint edges,and every subgraph of Qnk contains kn1 nodes. Thus,selecting a required edge or node costs O(kn1) time. Therefore, the time complexity of both HP-Round and HP-Direct is k(O(kn1)+O(kn1))=O(kn) .
HP-Round 和 HP-Direct 的主要时间成本在于 for 循环。这些 for 循环最多执行 k 次迭代。每次迭代调用 HP-PEF 并选择所需的边或节点。在 Qnk 的每个子图中调用 HP-PEF 构建路径 H 需要 kn3O(k2)=O(kn1) 时间。得到的 H 路径包含 kn112 个互不相交的边,且 Qnk 的每个子图包含 kn1 个节点。因此,选择所需的边或节点需要 O(kn1) 时间。因此,HP-Round 和 HP-Direct 的时间复杂度是 k(O(kn1)+O(kn1))=O(kn)
Line 4 costs O(n) time. Line 5 classifies all kn nodes of Qnk ,costing O(kn) time. Line 6 costs O(k) time. Lines 7-10 cost O(1) time. Lines 11-13 cost O(kn) time. Lines 14-15 cost O(kn) time. Line 17 costs O(kn) time. Line 18 costs O(kn1) time since there exist kn112 mutually disjoint edges of P in each subgraph. Line 19 costs O(kn) time. Line 20 costs O(1) time.
第 4 行需要 O(n) 时间。第 5 行对 Qnk 的所有 kn 节点进行分类,需要 O(kn) 时间。第 6 行需要 O(k) 时间。第 7-10 行需要 O(1) 时间。第 11-13 行需要 O(kn) 时间。第 14-15 行需要 O(kn) 时间。第 17 行需要 O(kn) 时间。第 18 行需要 O(kn1) 时间,因为在每个子图中存在 kn112 个互不相交的 P 边。第 19 行需要 O(kn) 时间。第 20 行需要 O(1) 时间。
Therefore,HP-PEF needs O(N) time.
因此,HP-PEF 需要 O(N) 时间。
In the following, we give a detailed example to explain how Algorithm HP-PEF embeds the H-path into Qnk under the PEF model. In the example,we set n=k=3,s=001 , and t=210 . Moreover,let F2={(100,200)},F1= {(001,011),(010,020),(210,220),(200,220),(201,221), (102,122),(002,022)},F0= . Obviously,we have e2=|F1|=7,e1=|F2|=1 ,and e0=|F0|=0 . Since |F1|>|F0|,|F2| ,the algorithm HP-PEF divides Q33 into 3 disjoint subgraphs Q[0],Q[1] ,and Q[2] along the 1-dimension. Since |F1[2,0]|>|F1[0,1]|,|F1[1,2]| ,we have l=2 ,which implies that the subsequent constructive process doesn't involve the edges between Q[2] and Q[0] . Next,the algorithm HP-PEF will take the node s as the source node a since s is closer to Q[2] along the clockwise than t . Correspondingly,the node t is deemed as the destination node b . Since la=0=l+1(mod3) and la=0lb=1 ,the algorithm HP-PEF calls the procedure HP-Direct to construct the H-path along the clockwise (i.e., d=1 ) by the approaches of Case 1.2 in Theorem III.2,where the H-path in Q[l] (isomorphic to Q23 ) with lZ3 is constructed by Algorithm 1. Fig. 7 shows the H-path constructed by Algorithm HP-PEF in Q33 ,where the dashed lines represent the faulty edges.
在以下内容中,我们给出了一个详细的示例,以解释算法 HP-PEF 如何在 PEF 模型下将 H 路径嵌入 Qnk 中。在示例中,我们设定 n=k=3,s=001 ,并且 t=210 。此外,令 F2={(100,200)},F1= {(001,011),(010,020),(210,220),(200,220),(201,221), (102,122),(002,022)},F0= 。显然,我们有 e2=|F1|=7,e1=|F2|=1 ,并且 e0=|F0|=0 。由于 |F1|>|F0|,|F2| ,算法 HP-PEF 将 Q33 划分为 3 个不相交的子图 Q[0],Q[1] ,并沿 1 维方向 Q[2]|F1[2,0]|>|F1[0,1]|,|F1[1,2]| 。由于 l=2 ,我们得到 Q[0] ,这意味着后续构造过程不涉及 Q[2]s 之间的边。接下来,算法 HP-PEF 将选择节点 a 作为源节点 t ,因为 a 沿顺时针方向比 b 更接近 Q[2] 。相应地,节点 b 被视为目标节点 la=0=l+1(mod3) 。由于 la=0lb=1d=1 ,算法 HP-PEF 调用过程 HP-Direct 沿顺时针方向(即 Q[l] )构造 H 路径,方法遵循定理 III.2 中的案例 1.2。其中,Q23 中的 H 路径(同构于 lZ3 )通过算法 1 构建。图 7 展示了算法 HP-PEF 在 Q33 中构造的 H 路径,其中虚线表示故障边。
Fig. 7. The H-path constructed by Algorithm HP-PEF in Q33 ,where the solid lines represent the fault-free edges and the dashed lines represent the faulty edges.
图 7。算法 HP-PEF 在 Q33 中构造的 H 路径,其中实线表示无故障边,虚线表示故障边。

V. Performance Analysis
V. 性能分析

In this section, we implement the algorithm HP-PEF by using Python programs and evaluate the performance of HP-PEF. We carry out the simulation by using a 2.80GHz Intel ®CoreTM i9-10900 CPU and 127 GB RAM under the Linux operating system.
在本节中,我们通过使用Python程序实现了算法HP-PEF,并评估了HP-PEF的性能。我们在Linux操作系统下,使用2.80GHz英特尔®CoreTM i9-10900 CPU和127 GB RAM进行了模拟。

A. Average Path Length
A. 平均路径长度

Along the H-path constructed by HP-PEF, we aim to compute the path length which is the number of edges between the source and destination nodes. We are interested in computing the path length since it's beneficial to evaluate the performance of HP-PEF for future applications to NoCs. Moreover, based on the following concerns,we choose the adjacent node pair in Qnk as the source and the destination to compute the path length:
沿着HP-PEF构建的H路径,我们旨在计算路径长度,即源节点和目标节点之间的边数。我们感兴趣于计算路径长度,因为这有助于评估HP-PEF在未来应用于NoCs的性能。此外,基于以下考虑,我们选择Qnk中的相邻节点对作为源节点和目标节点来计算路径长度:
1) When there exists no faulty edge in networks, the adjacent node pair possesses the shortest path length 1.
1) 当网络中不存在故障边时,相邻节点对具有最短路径长度1。
2) The algorithm HP-PEF can address large-scale edge faults. When the edge fault occurs, the path length of adjacent node pairs is naturally more sensitive to edge fault than other kinds of node pairs.
2) 算法HP-PEF能够处理大规模的边故障。当边故障发生时,相邻节点对的路径长度自然比其他类型的节点对对边故障更敏感。
3) Our method focuses on the distribution pattern of edge faults in each dimension. The path length of adjacent node pairs may be followed by the distribution pattern of edge faults. It's interesting to explore the relationship between the path length of adjacent node pairs and the number of edge faults in each dimension.
3) 我们的方法关注每个维度中边故障的分布模式。相邻节点对的路径长度可能会遵循边故障的分布模式。探索相邻节点对的路径长度与每个维度中边故障数量之间的关系是很有趣的。
TABLE I
EXPERIMENTAL SETTINGS
实验设置
Q33Q35Q37Q39Q43Q53Q63
Adjacent node pairs27×3125×3343×3729×381×4243×729×6
Faulty edges824488033112353
H-paths351775058653265356324029403265356
Q33Q35Q37Q39Q43Q53Q63
相邻节点对27×3125×3343×3729×381×4243×729×6
故障边824488033112353
H路径351775058653265356324029403265356
One edge corresponds to exactly one adjacent node pair. Thus, we define the dimension of an adjacent node pair as the dimension of the edge connecting it. By the definition of Qnk , there exist kni -dimensional edges,which implies that there exist kni -dimensional adjacent node pairs for each iZn . Then Qnk has nkn adjacent node pairs in total. As for the faulty edges,we directly set |F|=knk2k12n+5 to prevent the occurrence of |F2|==|Fn1| in the experimental process. Moreover, to make comparisons more obvious, we assume |Fn1||Fn2||F0| . Then we set |Fi|=ki2 with iZnZ2,|F1|=1 ,and |F0|=0 . Given a node pair(s,t) and a PEF set, the algorithm HP-PEF can generate an H-path between s and t . There exist (kn2)=k2nkn2 different node pairs (s,t). Thus,given a PEF set,the algorithm HP-PEF can generate k2nkn2 different H-paths. Our experimental settings are shown in Table I.
一个边对应于恰好一对相邻节点。因此,我们定义相邻节点对的维度为连接它的边的维度。根据 Qnk 的定义,存在 kni 维的边,这意味着对于每个 iZn 存在 kni 维的相邻节点对。那么 Qnk 总共有 nkn 对相邻节点。至于故障边,我们直接设置 |F|=knk2k12n+5 以防止实验过程中出现 |F2|==|Fn1| 。此外,为了使比较更加明显,我们假设 |Fn1||Fn2||F0| 。然后我们设置 |Fi|=ki2iZnZ2,|F1|=1 ,并且 |F0|=0 。给定一个节点对 (s,t) 和一个PEF集合,算法HP-PEF可以在 st 之间生成一条H路径。存在 (kn2)=k2nkn2 对不同的节点对 (s,t)。因此,给定一个PEF集合,算法HP-PEF可以生成 k2nkn2 条不同的H路径。我们的实验设置如表I所示。
In the simulation,we first randomly generate a PEF set F with |Fi|=ki2 for iZnZ2,|F1|=1 ,and |F0|=0 . Next, under the edge fault set F ,we utilize the algorithm HP-PEF to generate all possible H -paths,that is, k2nkn2 different H -paths. And then, according to the dimension of adjacent node pairs, we compute the average path length (APL for short) of them in all H -paths. More specifically,we denote the APL of each adjacent node pair in all H -paths as plij ,where iZn is the dimension of the adjacent node pair and jZkn is the unique identification of the adjacent node pair in the i -dimension. Then we compute the APLi for each dimension iZn as follows:
在模拟中,我们首先随机生成一个PEF集合 F ,包含 |Fi|=ki2 用于 iZnZ2,|F1|=1 ,以及 |F0|=0 。接着,在边缘故障集 F 下,我们使用算法HP-PEF生成所有可能的 H -路径,即 k2nkn2 个不同的 H -路径。然后,根据相邻节点对的维度,我们计算它们在所有 H -路径中的平均路径长度(简称APL)。更具体地说,我们表示每个相邻节点对在所有 H -路径中的APL为 plij ,其中 iZn 是相邻节点对的维度,jZkn 是在 i 维度中相邻节点对的唯一标识。然后我们按以下方式计算每个维度 iZnAPLi
APLi=jZknplijkn.
Simultaneously, we compute the standard deviation (SD for short) to evaluate the quantity of difference in path length as follows:
同时,我们计算标准差(简称SD),以评估路径长度差异的数量,如下所示:
SDi=jZkn(plijAPLi)2kn.
Fig. 8 shows the simulation results about the APLi of Qnk with different k and n . We observe that APLi is positively related to |Fi| . For example,the values of |F0| and |F1| differ by only 1,and APL1 is slightly higher than APL0 . The value of |Fi| with i2 is a power function with base k ,and APLi is much higher than APL0 and APL1 . In Qn3 ,the distance value between APLi+1 and APLi exhibits a sharper growth trend with larger i . Moreover,with increasing n and k ,we observe from the results that the growth rate of APLi is more sensitive to k than n . For example,in Q3k with increasing k from 3 to 9,the APL2 grows rapidly from 11.1 to 154.3. However,in Qn3 with increasing n from 3 to 6,the APL2 grows slowly from 11.1 to 17.7. Although k increment by 2 and n increment by 1 on the x -axis,the growth rate of APLi in Qn3 can still indicate the modest influence of n on APLi . This phenomenon may be caused by the fact that the value of |Fi| is only influenced by k ,independent of n . Fig. 9 shows the SDi of Qnk with different k and n . The growth trends for SDi and APLi are roughly the same. However,the parameter n can significantly affect the growth rate of SDi ,which is obviously different from that of APLi . It implies that the larger n and k , the more dispersed the values of path length.
图8显示了关于 APLi 的模拟结果,涉及不同 knQnk 。我们观察到 APLi|Fi| 正相关。例如,|F0||F1| 的值仅相差1,而 APL1 略高于 APL0 。带有 i2|Fi| 的值是一个以 k 为底的幂函数,且 APLi 远高于 APL0APL1 。在 Qn3 中,APLi+1APLi 之间的距离值在较大的 i 下呈现出更尖锐的增长趋势。此外,随着 nk 的增加,我们从结果中观察到 APLi 的增长率对 k 比对 n 更敏感。例如,在 Q3k 中,随着 k 从3增加到9,APL2 从11.1迅速增长到154.3。然而,在 Qn3 中,随着 n 从3增加到6,APL2 仅从11.1缓慢增长到17.7。尽管在 x -轴上 k 增加2而 n 增加1,但在 Qn3APLi 的增长率仍然可以表明 nAPLi 的适度影响。这种现象可能是由于 |Fi| 的值只受 k 影响,独立于 n 。图9显示了不同 knQnkSDiSDiAPLi 的增长趋势大致相同。然而,参数 n 可以显著影响 SDi 的增长率,这与 APLi 的增长率明显不同。这意味着 nk 越大,路径长度的值越分散。
Fig. 8. The APLi of adjacent node pairs in Qnk with different n and k .
图 8. 相邻节点对在 APLi 中的 Qnk 随不同的 nk 的变化。
Fig. 9. The SDi of adjacent node pairs in Qnk with different n and k .
图 9. 相邻节点对在 SDi 中的 Qnk 随不同的 nk 的变化。
Next,we compute the APL of all adjacent node pairs in Qnk as follows:
接下来,我们计算了 Qnk 中所有相邻节点对的 APL,如下所示:
APL=iZnjZknplijnkn.
Correspondingly, the SD of all adjacent node pairs is also computed:
对应地,所有相邻节点对的 SD 也被计算出来:
SD=iZnjZkn(plijAPL)2nkn.
In Fig. 10,we show the APL and SD of Qnk . For Q33 ,the SD is slightly smaller than APL. However,with increasing k and n ,the SD grows faster than the APL. In addition, from the simulation, we are aware of the following attractive phenomena. (1) For Q3k , the ratio of APL to |F| is about 1.3. With k increases,the value of |F|/ APL remains essentially the same. (2) For Qn3 ,the value of |F|/ APL varies approximately linearly with n . We list these results in Table II. As for what caused the positive correlation between n and |F|/APL ,there is currently no definite attribution. We roughly think that since the algorithm HP-PEF constructs the required H -path according to the distribution pattern of edge faults in each dimension, the H-path obtained is endowed with the nature of traversing all n dimensions,which results in an additional effect of n on the APL.
在图 10 中,我们展示了 Qnk 的 APL 和 SD。对于 Q33,SD 略小于 APL。然而,随着 kn 的增加,SD 的增长速度超过了 APL。此外,从模拟中,我们注意到了以下吸引人的现象。(1)对于 Q3k,APL 与 |F| 的比例约为 1.3。随着 k 的增加,|F|/ APL 的值基本保持不变。(2)对于 Qn3|F|/ APL 的值随 n 线性变化。我们将这些结果列在表 II 中。至于是什么导致了 n|F|/APL 之间的正相关,目前还没有确切的归因。我们大致认为,由于算法 HP-PEF 根据每个维度边缘故障的分布模式构建所需的 H -路径,得到的 H-路径具有穿越所有 n 维度的性质,这导致了 n 对 APL 的额外影响。
Fig. 10. The APL and SD of adjacent node pairs in Qnk with different n and k .
图 10. Qnk 中相邻节点对的 APL 和 SD 随不同的 nk 的变化。